import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/18 20:59
 * @description 最简单，用list存储
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        ListNode head = new ListNode(4, new ListNode(1, new ListNode(2, new ListNode(3))));
        solution.sortList(head);
    }
    public ListNode sortList(ListNode head) {
        if (head == null) {
            return null;
        }
        List<ListNode> list = new ArrayList<>();
        while (head != null) {
            list.add(head);
            head = head.next;
        }
        Collections.sort(list, (a, b) -> a.val - b.val);
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        for (int i = 0; i < list.size(); i++) {
            ListNode temp = new ListNode(list.get(i).val);
            cur.next = temp;
            cur = temp;
        }
        return dummy.next;
    }
}
